#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// extern int Add(const int& a, const int& b);
// int main()
// {
//     cout << "Hello World!" << endl;
//     int a = 10, b = 20;
//     cout << Add(a, b) << endl;
// }

/*
class Solution
{
public:
    string addString(string a, string b) 
    {
        string ret;
        int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;
        while (cur1 >= 0 || cur2 >= 0 || t)
        {
            if (cur1 >= 0) t += a[cur1--] - '0';
            if (cur2 >= 0) t += b[cur2--] - '0';
            ret += t % 10 + '0';
            t /= 10;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }

    string multiply(string num1, string num2)
    {
        返回值ret
        string ret("0");
        进制位
        for (int i = num2.size() - 1; i >= 0; --i)
        {
            int num_2 = num2[i] - '0';
            int next = 0;
            中间存放的临时string
            string tmp;
            处理后置0
            int n = num2.size() - 1 - i;
            while (n--) tmp += '0';
            for (int j = num1.size() - 1; j >= 0; --j)
            {
                int num_1 = num1[j] - '0';
                相乘两数都不为0
                if ((num_2 * num_1 + next) != 0)
                {
                    int total = num_2 * num_1 + next;
                    next = total / 10;
                    tmp += (total % 10 + '0');
                }
                else
                {
                    tmp = "0";
                }
            }
            if (next)
                tmp += (next + '0');
            将tmp(reverse)加给ret
            reverse(tmp.begin(), tmp.end());
            ret = addString(ret, tmp);
        }
        
        return ret;
    }
};

int main()
{
    string a = "721";
    string b = "140";
    cout << Solution().multiply(a, b) << endl;
    return 0;
}
*/


/*Definition for a binary tree node.*/
struct TreeNode {
     int val;
     TreeNode *left;
    TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution 
{
    // 两个全局变量(ret + count)
    int ret = 0, count = 0;
public:
    int dfs(TreeNode* root, int count)
    {
        // 中序遍历
        if(root == nullptr)
            return count;
        count = kthSmallest(root->left, count);
        if(count == 0) return ret;
        if(count == 0)
        {
            ret = root->val;
            return ret;
        }
        count--;
        count = kthSmallest(root->right, count);
        return count;
    } 
    int kthSmallest(TreeNode* root, int k) 
    {
        count = k;
        return dfs(root, count);
    }
};

int main()
{
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);
    int k = 1;
    Solution().kthSmallest(root, k);
    delete root;
    return 0;
}